﻿using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.PriorityQueues;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Knapsack.BranchAndBound
{
    public class KnapsackSolver1 : KnapsackSolver0
    {
        public KnapsackSolver1(IList<int> weights, IList<double> values)
            : base(weights,values)
        {
        }

        public override IList<int> Solve(int W)
        {
            var item = new State(_values.Sum(), 0.0, 0, new int[] { }.ToAlgoritmiaList());
            var open = new MaxHeap<State>(new[] { item });
            var ramifications = new[] { 0, 1 };
            IList<int> solution = null;
            double optimalValue = double.NegativeInfinity;
            while (open.Count > 0)
            {
                var s = open.ExtractOptimal();
                foreach (var decision in ramifications)
                {
                    var x = s.Decisions.Concat(new[] { decision }).ToAlgoritmiaList();
                    var knownWeight = s.KnownWeight + decision * _weights[x.Count - 1];
                    var knownValue = s.KnownValue + decision * _values[x.Count - 1];
                    if (x.Count == _n)
                    {
                        if (knownWeight <= W && knownValue > optimalValue)
                        {
                            solution = x;
                            optimalValue = knownValue;
                        }
                    }
                    else
                    {
                        var score = knownValue + _values.Where((e, i) => i >= x.Count).Sum();
                        open.Add(new State(score, knownValue, knownWeight, x));
                    }
                }
            }
            return solution;
        }
    }
}
